package Sort.sort2016;

public class HeapSort {

	public static void main(String[] args) {
		int[] array={9,7,8,6,5,4,3,2,1};
		heapSort(array);
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]);
		}
	}
	public static void heapSort(int[] array){
		if(array==null||array.length==0){
			return;
		}
		//构建最大堆
		for(int i=array.length/2-1;i>=0;i--){
			adjustHeap(array,i,array.length-1);
		}
		for(int i=array.length-1;i>=0;i--){
			int temp = array[i];
			array[i] = array[0];
			array[0] = temp;
			adjustHeap(array, 0, i-1);
		}
	}
	//调整后再次构建最大堆
	public static void adjustHeap(int[] array,int index,int end){
		for(int j=2*index+1;j<=end;j=2*j+1){
			if(j<end&&array[j]<array[j+1]){
				j++;
			}
			if(array[index]>=array[j]){
				break;
			}
			int temp = array[index];
			array[index] = array[j];
			array[j] = temp;
			index=j;
		}
	}

}
